This invention relates in general to the timing of intervals in a computer and more specifically to a system providing an interval timing service for processes running in a computer system.
Different types of interval timers can be found in alarm clocks, egg timers, or timers in VCRs. Interval timers are used to cause an alarm or other pre-determined action to occur after a pre-specified amount of time. Within computer systems, interval timers are used in communications over networks, such as for re-transmitting a packet of communications data when a response does not arrive within the expected amount of time. Interval timers are also used in interactions with hardware devices, for error detection and handling, for detecting and handling failures within fault-tolerant systems, for pacing the rate at which displays are updated, in interactions with human beings, for dividing "CPU time" equitably among computer processes, and for a wide variety of other uses.
Some computer systems require the maintenance, or scheduling, of many events that are controlled by an interval timer or timers. Various schemes have been adopted to improve the efficiency of such timers and scheduling because the processing overhead required to update the timers and handle the events can become significant and degrade the ability of the computer to handle other tasks. An example of an approach to handling multiple timers is described in a paper by G. Varghese and T. Lauck entitled "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility," Proceedings of the Eleventh ACM Symposium on Operating System Principles, Nov. 8-11, 1987, Operating System Review 21 (5), ACM Press, 1987, ISBN 0-89791-242-X.
The system described by Varghese and Lauck, places emphasis on a "Timer Start" function. In accordance with Varghese and Lauck the timing method can be described by use of a hierarchy of timing wheels using "hours" "minutes" and "seconds" wheels to time delays of up to 24 hours with one-second resolution. This could be part of a larger hierarchy of timing wheels, allowing timing, for example, for up to 16 weeks.
For example, Varghese and Lauck consider the case where the current time is 10:24:30 and an interval of 50 minutes and 45 seconds is to be timed.
In the following:
______________________________________ curTime is the current time, or some regularly updated similar value. Since we are only interested in measuring intervals of time, curTime need not be the same as the true current time, it only needs to be advancing at the same rate. Also, it need not be directly updated by timing hardware, but it must be possible to access the timing hardware in order to learn the correct value for curTime. timeoutValue is the specified amount of time to elapse before the timer expires. expirationTime is the time at which the timer is to expire, if not previously canceled. That is, the timer expires when curTime becomes equal to expirationTime. ______________________________________
The method for Timer Start is one of first computing the expiration time, and then enqueuing (chaining) the timer on the most-significant wheel for which the expiration time differs from the current time:
______________________________________ curTime is 10:24:30 timeoutValue is 00:50:45 expirationTime is 11:15:15 ______________________________________
According to this prior method, the timer will be chained on the hours wheel in slot 11. This happens because expirationTime differs from curTime in the hours position, and the hours portion of expirationTime is 11.
Then, if the client doesn't cancel the timer, at 11:00:00 the timer will be moved to slot 15 of the minutes wheel. At 11:15:00, the timer is moved again, to slot 15 of the seconds wheel. The timer finally expires at 11:15:15 and is no longer on any slot of any timing wheel, until it's re-used to time another interval of time.
Although Varghese and Lauck describe a relatively efficient timer processing mechanism, it is desirable to provide a timer system that further reduces the processing required by a computer to operate and maintain the timers.